package com.hnlwh.sort;

import com.hnlwh.utils.SortUtils;

import java.util.Random;

/**
 * @program: sortingalgorithm
 * @description: 归并排序
 * @author: yuhui
 * @date: 2021-07-27 23:48
 */
public class MergeSort {
    public static void main(String[] args) {


        int lenth=100000;
        int[] array=new int[lenth];
        for (int i = 0; i < array.length; i++) {
            array[i]=new Random().nextInt();
        }

        int[] tmp = new int[array.length];
        long start=System.currentTimeMillis();
        mergeSort(array,0,array.length-1,tmp);
        long end=System.currentTimeMillis();
        for ( int i: array
             ) {
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.println("---------耗时-------");
        System.out.println(end-start);

        System.out.println("========================");

        long start2 = System.currentTimeMillis();
        SortUtils.selectionSort(array);
        long end2 = System.currentTimeMillis();
        System.out.println("-----selectionSort耗时-----");
        System.out.println(end2-start2);
    }
    public static void merge(int[] array, int low ,int mid,int high,int[] tmp){
        int i = 0;
        int j = low ,k = mid+1;  // 定义 左边与右边序列的索引
        while (j <= mid && k <= high){
            if (array[j] < array[k]){
                tmp[i++] = array[j++];
            }
            else{
                tmp[i++] = array[k++];
            }
        }
        // 若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while (j<=mid){
            tmp[i++] = array[j++];
        }
        while (k<=high){
            tmp[i++] = array[k++];
        }
        for (int d = 0;d<i;d++){
            array[low+d]=tmp[d];
        }
    }

    public static void mergeSort(int[] array, int low ,int high,int[] tmp){
        if (low<high){
            int mid=(low+high)/2;
            mergeSort(array,low,mid,tmp);//对左边进行排序
            mergeSort(array,mid+1,high,tmp);//对右边进行排序
            merge(array,low,mid,high,tmp);//合并两个有序序列
        }
    }
}
